package algorithm.niuke;

public class J超级次方 {
    /*
     * 你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。
     * 
     * 示例 1:
     * 
     * 输入: a = 2, b = [3] 输出: 8 示例 2:
     * 
     * 输入: a = 2, b = [1,0] 输出: 1024
     */
    boolean log = false;

    public int superPow(int a, int[] b) {
        return fun2(a, b);
    }

    int fun1(int a, int[] b) {
        int len = b.length;
        int res = 1;
        int pow = a % 1337;
        int index = len - 1;
        while (index >= 0) {
            res = res * pow(pow, b[index], 1337);
            res %= 1337;
            pow = pow(pow, 10, 1337);
            index--;

        }
        return (int) res;
    }

    int pow(int base, int n, int mod) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return base;
        }
        return pow(base, n / 2, mod) * pow(base, n - n / 2, mod) % mod;
    }

    int fun2(int a, int[] b) {
        int res = 1;
        a %= 1337;
        for (int num : b) {
            res = pow(res, 10, 1337) * pow(a, num, 1337) % 1337;
        }
        return res;
    }

    int fun3(int a, int[] b) {
        /*
         * a^b %c == a^(b%phi(c)) % c
         */
        int phi = 1140;
        a %= 1337;
        int exp = 0;
        for (int num : b) {
            exp = exp * 10 + num;
            exp %= phi;
        }
        return pow(a, exp, 1337);
    }

    public static void main(String[] args) {
        int a = 3;
        int[] b = { 1, 0 };
        J超级次方 run = new J超级次方();
        run.superPow(a, b);
    }
}
